class Solution {
    /**
     * dfs坑点1：已经遍历过的节点不能够再遍历，用visit标记走过的路
     *
     * 坑点2：对于一个位置，可能有两条路要走，所以往方向1走后( visit[x]=1 )，还需要要退回来 ( visit[x]=0 )
     *                      visit[tx][ty] = 1;
     *                      dfs(board, word, tx, ty, index + 1);
     *                      visit[tx][ty] = 0;
     * 坑点3：visit可以不用每次都初始化，因为dfs弹出栈后这个位置会重新置为0，
            需要注意的是第30行 也要置为0，因为这个位置可能是中间的位置
     */
    int[][] nex = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int[][] visit;
    int row, col;
    boolean res = false;
    public boolean exist(char[][] board, String word) {
        row = board.length;
        if (row == 0 || word.length() == 0)
            return false;
        else
            col = board[0].length;
        visit = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visit[i][j] = 1;
                    dfs(board, word, i, j, 1);
                    if (res)
                        return true;
                    visit[i][j] = 0;
                }
            }
        }
        return false;
    }

    public void dfs(char[][] board, String word, int x, int y, int index) {
//        System.out.println(x + "," + y + " " + board[x][y]);
        if (index == word.length()) {
            res = true;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + nex[i][0];
            int ty = y + nex[i][1];
            if (tx < 0 || tx >= row || ty < 0 || ty >= col)
                continue;
            if (board[tx][ty] != word.charAt(index) || visit[tx][ty]==1)
                continue;
            visit[tx][ty] = 1;
            dfs(board, word, tx, ty, index + 1);
            visit[tx][ty] = 0;
        }
    }
}